package server.simple100;


import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/***
 * 94. 二叉树的中序遍历
 *
 *  中序遍历 -- 左 中 右
 *  前序遍历 -- 中 左 右
 *  后序遍历 -- 左 右 中
 *
 */
public class LeetCode94 {


    @Test
    public void test() {
        // 1,null,2,3
        //
        //       1
        //  null   2
        //       3
        //TreeNode treeNode1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
        TreeNode treeNode1 = new TreeNode(1 );
        inorderTraversal(null);
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        if(root==null){
            return vals;
        }
        nextNode(root, vals);
        return vals;
    }


    public void nextNode(TreeNode root, List<Integer> vals) {

        if (root.left != null) {
            nextNode(root.left, vals);
        }
        vals.add(root.val);
        if (root.right != null) {
            nextNode(root.right, vals);
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

//    给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
//
//        如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
//
//         
//
//        示例 1：
//
//
//        输入：p = [1,2,3], q = [1,2,3]
//        输出：true
//        示例 2：
//
//
//        输入：p = [1,2], q = [1,null,2]
//        输出：false
//        示例 3：
//
//
//        输入：p = [1,2,1], q = [1,1,2]
//        输出：false
//         
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/same-tree
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。